package main

import (
	"fmt"
)

type BST struct {
	root *node
	count int
}

type node struct {
	key int
	value string
	left *node
	right *node
}

func (b *BST) insert(n *node, key int, value string) *node {

	if n == nil {
		b.count++
		node := new(node);
		node.key = key
		node.value = value
		return node
	}

	if key == n.key {
		n.value = value
	} else if key > n.key {
		n.right = b.insert(n.right, key, value)
	} else {
		n.left = b.insert(n.left, key, value)
	}

	return n
}

func (b *BST) contain(n *node, key int) bool {

	if n == nil {
		return false
	}

	if key == n.key {
		return true
	} else if key > n.key {
		return b.contain(n.right, key)
	} else {
		return b.contain(n.left, key)
	}
}

func (b *BST) search(n *node, key int) (value interface{}) {

	if n == nil {
		return nil
	}

	if key == n.key {
		return n.value
	} else if key > n.key {
		return b.search(n.right, key)
	} else {
		return b.search(n.left, key)
	}
}

func (b *BST) preOrder(n *node) {

	if n == nil {
		return
	}

	fmt.Println(n.key, "---", n.value)
	b.preOrder(n.left)
	b.preOrder(n.right)
}

func (b *BST) inOrder(n *node) {

	if n == nil {
		return
	}

	b.inOrder(n.left)
	fmt.Println(n.key, "---", n.value)
	b.inOrder(n.right)
}

func (b *BST) postOrder(n *node) {

	if n == nil {
		return
	}

	b.postOrder(n.left)
	b.postOrder(n.right)
	fmt.Println(n.key, "---", n.value)
}

//func (b *BST) levelOrder(n *node) {
//
//	if n == nil {
//		return
//	}
//
//	b.postOrder(n.left)
//	b.postOrder(n.right)
//	fmt.Println(n.key, "---", n.value)
//}

func (b *BST) maxDepth (n *node) int {

	if n == nil {
		return 0
	}

	if b.maxDepth(n.left) >= b.maxDepth(n.right) {
		return b.maxDepth(n.left) + 1
	} else {
		return b.maxDepth(n.right) + 1
	}
}

func (b *BST) getMax (n *node) *node {

	if n.right == nil {
		return n
	}

	return b.getMax(n.right)
}

func (b *BST) getMin (n *node) *node {

	if n.left == nil {
		return n
	}

	return b.getMin(n.left)
}

func (b *BST) removeMin(n *node) *node {
	if n.left == nil {
		rightNode := n.right
		n = nil
		return rightNode
	}

	n.left = b.removeMin(n.left)

	return n
}

func (b *BST) removeMax(n *node) *node {
	if n.right == nil {
		leftNode := n.left
		n = nil
		return leftNode
	}

	n.right = b.removeMax(n.right)

	return n
}

func (b *BST) remove(n *node, key int) *node {

	if key < n.key  {
		n.left = b.remove(n.left, key)
		return n
	} else if key > n.key {
		n.right = b.remove(n.right, key)
		return n
	} else {

		if n.left == nil {
			rightNode := n.right
			n = nil
			return rightNode
		} else if n.right == nil {
			leftNode := n.left
			n = nil
			return leftNode
		}

		successor := b.getMin(n.right)
		successor.right = b.removeMin(n.right)
		n = nil
		return  successor
	}
}


func main() {
	bst := new(BST)
	bst.root = bst.insert(bst.root, 10, "aaa")
	bst.insert(bst.root, 8, "bbb")
	bst.insert(bst.root, 11, "ccc")
	bst.insert(bst.root, 6, "ddd")
	bst.insert(bst.root, 9, "ccc")
	bst.insert(bst.root, 30, "eee")

	bst.inOrder(bst.root)

	fmt.Println(bst.remove(bst.root, 6))

	bst.inOrder(bst.root)


}